home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / gnustuff / minix / libsrc~1.z / libsrc~1 / bsearch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-12-28  |  1.1 KB  |  56 lines
  1. #include "lib.h"
  2.  
  3. /*  bsearch(3)
  4.  *
  5.  *  Author: Terrence Holm          Aug. 1988
  6.  *
  7.  *
  8.  *  Performs a binary search for a given <key> within a sorted
  9.  *  table. The table contains <count> entries of size <width>
  10.  *  and starts at <base>.
  11.  *
  12.  *  Entries are compared using keycmp( key, entry ), each argument
  13.  *  is a (char *), the function returns an int < 0, = 0 or > 0
  14.  *  according to the order of the two arguments.
  15.  *
  16.  *  Bsearch(3) returns a pointer to the matching entry, if found,
  17.  *  otherwise NULL is returned.
  18.  */
  19.  
  20. #ifndef NULL
  21. #define  NULL    (char *) 0
  22. #endif
  23.  
  24.  
  25. _VOIDSTAR bsearch( key, base, count, width, keycmp )
  26.   _CONST _VOIDSTAR key;
  27.   _CONST _VOIDSTAR base;
  28.   unsigned int count;
  29.   unsigned int width;
  30.   int  (*keycmp)(_CONST _VOIDSTAR, _CONST _VOIDSTAR);
  31.  
  32.   {
  33.   _VOIDSTAR mid_point;
  34.   int  cmp;
  35.  
  36.   while ( count > 0 )
  37.     {
  38.     mid_point = base + width * (count >> 1);
  39.  
  40.     cmp = keycmp( key, mid_point );
  41.  
  42.     if ( cmp == 0 )
  43.     return( mid_point );
  44.  
  45.     if ( cmp < 0 )
  46.     count >>= 1;
  47.     else
  48.     {
  49.     base  = mid_point + width;
  50.     count = (count - 1) >> 1;
  51.     }
  52.     }
  53.  
  54.   return( NULL );
  55.   }
  56.